package com.lxm.leetcode;

/**
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * <p>
 * 一般来说，删除节点可分为两个步骤：
 * <p>
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-node-in-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * root = [5,3,6,2,4,null,7]
 * key = 3
 * <p>
 * 5
 * / \
 * 3   6
 * / \   \
 * 2   4   7
 * <p>
 * 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * <p>
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * <p>
 * 5
 * / \
 * 4   6
 * /     \
 * 2       7
 * <p>
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 * <p>
 * 5
 * / \
 * 2   6
 * \   \
 * 4   7
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-node-in-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Question450 {

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        TreeNode p = root;
        TreeNode pa = root;
        while (p != null) {
            if (p.val == key) {
                if (p.left == null || p.right == null) {
                    if (p == pa.left) {
                        pa.left = null;
                    } else {
                        pa.right = null;
                    }
                    return root;
                } else {
                    TreeNode pt = p.left;
                    TreeNode ppt = p.left;
                    while (pt.left != null) {
                        ppt = pt;
                        pt = pt.left;
                    }
                    ppt.left = null;
                    if (p == pa.left) {
                        pa.left = pt;
                    } else {
                        pa.right = pt;
                    }
                    pt.left = p.left;
                    pt.right = p.right;
                    return root;
                }
            } else if (p.val < key) {
                pa = p;
                p = p.right;
            } else {
                pa = p;
                p = p.left;
            }

        }
        return root;
    }

    public static void main(String[] args){
        TreeNode l3_1 = new TreeNode(2, null, null);
        TreeNode l3_2 = new TreeNode(4, null, null);
        TreeNode l3_3 = new TreeNode(7, null, null);
        TreeNode l2_1 = new TreeNode(3, l3_1, l3_2);
        TreeNode l2_2 = new TreeNode(6, null, l3_3);
        TreeNode l1_1 = new TreeNode(5, l2_1, l2_2);
        Question450  test = new Question450();
        TreeNode result = test.deleteNode(l1_1,3);
        System.out.println(result);
    }
}
